Hey guys,

I was looking into navigation meshes combined with a* pathfinding with help from this article http://www.ai-blog.net/archives/000152.html and I a bit confused about some of the concepts and use and need some help with the idea behind the creation. (I have used a* before in a tile based map)

1. how do you create a navigation mesh
2. how do you decide where the nodes are and which connect to each other (though i guess its based on neighbours), is it does by each polygon or the edges (ect) and from, are the nodes placed by the programmer e.g. this http://jceipek.com/Olin-Coding-Tutorials/img/Pathing/Island-NavMesh-Nodes.png or this http://s252.photobucket.com/user/PaulTozour/media/Stormwind-NavMesh.jpg.html
3. This question kinda ties into 2 and is one of the biggest things i dont understand, when it comes to this picture http://s252.photobucket.com/albums/hh9/PaulTozour/?action=view&current=Halaa_navmesh2_AB.jpg, what nodes is it using to plan that path. I know that the polygons define open and free to walk space but even so it needs nodes to compute the best path. does it auto create nodes on the edges of the polygons?

Another question i have is when it comes to making an rts would it be best to just do a 2d tile map on to of a 3d map or use a navmesh aswell.

Thanks for the help and any additional information would be appropriated (also any idea of how i would go around doing this is c++ would be helpful aswell)

There are probably in the neighborhood of 3 million posts, articles, and even tutorials on the internet on how to create navmeshes. It would probably be more economical for you to find those rather than expecting people to retype thousands of words here in response to you. Just saying that it isn't something that can (or should) be answered in a message board.

I'm working on a 2D plane, although the game is rendered in 3D (Think Diablo III - style) The way I'm pursuing it, based on some googling, reading blog posts etc. is creating a navmesh, connecting reflex vertices with all reflex vertices (except some that can be omitted) and making a hashtable-based graph. Then connecting start and end points to the graph before running A*.

I just posted a bit on how I exclude nodes:

http://www.gamedev.net/topic/670853-excluding-vertices-from-polygonal-roadmap-for-pathfinding/

If you want I can expand on the subject - just spent a good amount of energy optimizing the connection of start and endpoints to the graph.

ATM I'm also working on also including a grid based index to optimize things further.

There really isn't a wrong way to create a navigation mesh, as long as it's a graph. That's all it really is.

The navigation mesh, is quite literally a mesh, as it's major verticies are used to define large areas of space which something is capable of moving in.

There are a large variety of ways to do this, and they all solve basically the same issues in different manners.

Typically the most common form of navigation with nav meshes would be to go the mid point of a poly, and exit off of an edge or a vertex

Obviously you can see that this leads to a problem of zig zagging. To circumvent this, you approximate in a variety of ways.

One method....
Use the method mentioned above, and collapse lines together for an optimal path.

now you need to add a bit of a mechanism for this path to feel more smooth. So you treat the line like a curve, and you change all end points into curves.

Now when your characters follow the path, they do so in a loose fashion. They use the physics engine to help guide them around this path while an animation plays.

The biggest benefit of the navmesh is that it allows you to travel through a large world much more loosely than your typical node graph. But... in larger scales it can run slower as well.

I guess you could build a LOD for the navmesh... or create a system that does it for you.

Now... for A*.

A* will work very much the same as it would on any other graph system. As long as you remember one key factor. A* is not a library. It's an algorithm. This means that you need to make sure to do the work needed to have it working on your system.

It won't be hard if you remember how it works.

A star works by calculating the cost to move one position from the current position to the end point. As it scans the graph, it stores the costs for all the paths it can take before settling with the most optimal.

Notice how A* makes use of a grid? Well... what is a Navmesh? Usually a grid of Squares or Triangles. And if you wish to support it... an Ngon.

The details on how to store this will be up to you.